package com.qst.sort;

import java.util.Arrays;

/**
 * @author 刘汉平
 * @date 2019/9/8 13:22
 * 直接插入排序
 */
public class insertSort {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 4, 7, 2, 8};
        insertSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void insertSort(int[] nums) {
        //先遍历数组，从第二个元素开始遍历
        for (int i = 1; i < nums.length; i++) {
            //把当前遍历的元素存起来
            int temp = nums[i];
            int j;
            //遍历当前元素，前面所有的元素，如果前面的元素比你存的元素大，那么下标就往前走
            for (j = i - 1; j >= 0 && nums[j] > temp; j--) {
                //把大的元素替换到后一个数字
                nums[j+1] = nums[j];
            }
            //如果比存的临时变量小，就把你村的这个数字插到这个变量的前面
            nums[j + 1] = temp;
        }
    }
}
